//
// Created by lanlu on 2025/8/14.
//

#include <algorithm>
#include <utility>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr){}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){}
};

class Solution {
public:
    int rob(TreeNode* root) {
        pair<int, int> ans = dfs(root);
        return max(ans.first, ans.second);
    }

    // 深度优先的后序遍历
    // 返回偷窃当前节点的最大金额和不偷当前节点的最大金额
    // <偷, 不偷>
    pair<int,int> dfs(TreeNode* root)
    {
        // 递归出口
        if (!root) return {0, 0};

        // 先递归处理左右子树
        pair<int,int> left = dfs(root->left);
        pair<int,int> right = dfs(root->right);

        // 偷当前节点  rob[node] = node.val + not_rob[left] + not_rob[right]
        int rob = root->val + left.second + right.second;
        // 不偷当前节点的收益 not_rob[node] = max(rob[left],not_rob[left]) +  max(rob[right],not_rob[right])
        int notRob = max(left.first, left.second) + max(right.first, right.second);
        return {rob, notRob};
    }
};